package org.xiaojinlong.exam;

/**
 * @author Jin Long
 *         2016/6/27
 */
public class T160627 {
    private static class Node<Item> {
        Item value;
        Node<Item> next;

        Node(Item value, Node<Item> next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return this.value.toString();
        }
    }

    static <Item> Node<Item> findKthToTail(Node<Item> head, int k) {
        if (head != null && k > 0) {
            Node<Item> p = head;
            for (int i = 0; i < k-1; i++) {
                if (p.next == null) {
                    return null;
                } {
                    p = p.next;
                }
            }

            Node<Item> q = head;
            while (p.next != null) {
                p = p.next;
                q = q.next;
            }

            return q;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        Node<String> head = new Node<>("a", new Node<>("b", new Node<>("c", new Node<>("d", null))));
        System.out.println(findKthToTail(head, 2));
    }
}
